package array

import "math"

// https://leetcode-cn.com/problems/increasing-triplet-subsequence/
// 递增的三元子序列
// 算法: 贪心+遍历，一直记录当前满足题意的最优子序列
// 时间复杂度: O(n)
func IncreasingTriplet(nums []int) bool {
	if len(nums) < 3 {
		return false
	}

	var start, end int
	currentMin := math.MaxInt32
	// 先找到第一个递增的相邻节点
	index := 0
	for index < len(nums)-1 {
		if nums[index] < nums[index+1] {
			start = nums[index]
			end = nums[index+1]
			currentMin = start
			break
		}
		index++
	}
	if index == len(nums)-1 {
		return false
	}

	// 继续遍历
	for index < len(nums) {
		switch {
		case nums[index] > end:
			// start, end, 当前节点 可以作为子序列
			return true
		// 优先借助历史最小值，替换当前递增队列，注意如果当前节点比 end 还要大，那就也没必要替换队列了
		case currentMin < nums[index] && nums[index] <= end:
			start = currentMin
			end = nums[index]
		case nums[index] > start && nums[index] <= end:
			// 队列缩为更接近答案的
			end = nums[index]
		// 记录当前最小值，方便在第二个 case 中替换队列
		case nums[index] <= start:
			if nums[index] < currentMin {
				currentMin = nums[index]
			}
		}
		index++
	}
	return false
}
